/**
 * @author LKQ
 * @date 2022/1/6 10:51
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 1, 1, 2};
        System.out.println(solution.rob(nums));
    }

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        if (n == 1) {
            // 只有一一间房间
            return nums[0];
        }
        // dp[i] 为 [0,i]房屋所偷全部金额 dp[i] = Max(dp[i-2] + num[i], dp[i-1]);
        int[] dp = new int[n];
        dp[0] =nums[0];  dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i-2]  + nums[i], dp[i-1]);
        }
        return dp[n-1];
    }

    public int rob2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        if (n == 1) {
            // 只有一一间房间
            return nums[0];
        }
        // dp[i] 为 [0,i]房屋所偷全部金额 dp[i] = Max(dp[i-2] + num[i], dp[i-1]); 优化为滚动数组
        int first =nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}
